package cn.xiaolang.function.sort_algorithm;

/**
 * 选择排序
 * 
 * @author fuhw/DeanKano
 * @date 2018-11-28
 */
public class ChoiceSort extends AbstractSort {

	/**
	 * 1.从待排序待元素中挑选中最小的元素 
	 * 2.如果最小元素不是待排序的第一个元素,那么将它和第一元素互换 
	 * 3.从剩余的n-1个中找出最小的元素,重复1,2步骤
	 */
	@Override
	public void sort(int[] a) {
		int arrLen = a.length;
		// 循环趟数arrLen-1
		for (int i = 0; i < arrLen - 1; i++) {
			// 每一趟最小值数组下标，初始第一个数字为这趟的最小值
			int minIndex = i;
			// 找出每一趟的最小值，如果有最小值就将这趟的最小值放在这趟数组第一个位
			for (int j = i + 1; j < arrLen; j++) {
				if (a[j] < a[minIndex]) {
					minIndex = j;
				}
			}
			// 交换这趟的第一个数字和最小值
			exchange(a, i, minIndex);
		}
	}

	private static void exchange(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}
